A network element for routing packets (e.g., Internet Protocol (“IP”) packets, Ethernet packets, etc.) typically includes a number of slots for receiving line cards. Each line card has one or more ports for connecting media on which packets can be received. In order to process the packets, the network element will include one or more packet processors. For example, each line card will include one or more packet processors.
A packet processor on a line card that processes packets coming into the network element (an ingress or egress packet processor) will typically be processing packets from several different “micro-flows” at a time. A micro-flow describes all of the packets transmitted from the same address and port to the same destination address and port as part of an exchange of information between two applications during a given time period (e.g., a Transmission Control Protocol session). While packet protocols (such as the IP packet protocol) allow the destination to correct for the reception of out-of-order packets from a given micro-flow, such correction slows performance. Thus, many network elements are designed to prevent packet reordering by ensuring that the packets of a given micro-flow received on the same interface are transmitted out of the network element in the order in which those packets were received by the network element.
One packet processor design includes multiple execution units and scheduling/reordering software. The scheduling/reordering software, running on one or more of the execution units, is used to control the processing of the packets being received by the packet processor. This software operates such that the order in which the packets are transmitted out of the packet processor is the same as the order in which they were received (referred to herein as “globally” in order), but allows, to a certain extent, the packets to be processed out-of-order. The global ordering ensures that the ordering of the packets of a given micro-flow received on a given interface is maintained, while the out-of-order processing between unrelated micro-flows allows for improved performance.
In particular, the software (executing on the multiple execution units) maintains a separate queue for each slot/line card. The software assigns each incoming packet (based on the packet's header) to the queue for the line card over which that packet will be transmitted out of the network element. Therefore, the packets from a given micro-flow received at a given interface will all be assigned to the same queue, and multiple micro-flows are typically assigned to the same line card queue. When an execution unit is freed up for processing another packet, the software determines from which line card queue the next packet is selected for processing. In addition, the software tracks the order in which the packets are removed from each queue. Once the packet has been processed, the packets are placed on a completed line card processing queue which maintains the original order assigned of the line card queue. This ensures that the processed packets of a micro-flow queue can be made to exit the packet processor in the same order as they were received.
One disadvantage of this packet processor design is that the scheduling/reordering software requires a relatively large amount of the processing power provided by the execution units of the packet processor. Another disadvantage of this packet processor design is that although different packets take different amounts of time to process, the packets must exit the packet processor in the order in which they were received (due to the global ordering). As a result, a packet that is taking a relatively significant amount of time to process can prevent later received, but already processed packets from exiting the packet processor.